#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;

class time{
    public:
    int hour;//小时
    int minute;//分钟
    void init(int hour,int minute){//初始化
        this->hour=hour;
        this->minute=minute;
    }
    void init(time t1){
        this->hour=t1.getHour();
        this->minute=t1.getMinute();
    }
    void change(int hour,int minute){//修改时间
        this->hour=hour;
        this->minute=minute;       
    }
    void show(){//显示时间
        cout<<hour<<':'<<minute<<endl;
    }
    int getHour(){//得到小时
        return hour;
    }
    int getMinute(){//得到分
        return minute;
    }
    time add(int t1){//加法，用于计算开始时间，结束时间
        int thour=t1/60;
        int tminute=t1%60;
        time t;
        if(minute+tminute<60){
            t.init(hour+thour,minute+tminute);  
        }else{
            minute=(minute+tminute)%60;
            hour=hour+thour+1;
            t.init(hour,minute);
        }
        return t;
    }
    int substract(time t1){//计算时间差
        int tminute=t1.minute-this->minute;
        int thour;
        if(tminute<=0){
            t1.hour-=1;
            tminute+=60;
        }
        thour=t1.hour-this->hour;

        return thour*60+tminute;
    }
    bool than(time t1){//比较时间大小，小返回true
        if(this->hour<t1.hour){
            return true;
        }else if(this->hour==t1.hour && this->minute<=t1.minute){
            return true;
        }else{
            return false;
        }
    }
};

class Job{

    public:
    string jobname;//作业名
    time intime;//进入时间
    string state;//状态
    int runtime;//运行时间
    time begintime;//开始运行时间
    time endtime;//运行结束时间
    double cycletime;//周转时间
    double wcycletime;//带权周转时间
    double rrn;//响应比
    int rank;//优先级
    int resruntime;//剩余运行时间

    void init(string jobname,time intime,int runtime,int rank){//初始化作业状态
        this->jobname=jobname;
        this->intime.init(intime);
        this->runtime=runtime;
        state="wait";
        this->begintime.init(0,0);
        this->endtime.init(0,0);
        this->rank=rank;
        cycletime=0;
        wcycletime=0;
        rrn=0;
    }
    void setbegintime(time t){//修改开始时间
        begintime.init(t);
    }
    void setendtime(time t){//修改结束时间
        endtime.init(t);
    }
    void setcycle(){//修改周转时间和带权周转时间
        cycletime=this->intime.substract(this->endtime);
        wcycletime=cycletime/this->runtime;
    }
    void setrrn(time t1){//1+等待时间/运行时间  等待时间=上一个作业完成时间-作业进入时间
        int waittime=this->intime.substract(t1);
        this->rrn=1+waittime/runtime;
    }
    void setstate(string t){//设置状态
        this->state=t;
    }
    int getcycletime(){//得到周转时间
        return cycletime;
    }
    int getwcycletime(){//得到带权周转时间
        return wcycletime;
    }  
    void show(){//输出
        cout<<jobname<<" ";
        cout<<"进入时间："<<intime.hour<<":"<<intime.minute;
        //intime.show();
        cout<<"  运行时间："<<runtime<<" "<<"开始运行时间： "<<begintime.hour<<":"<<begintime.minute;
        //begintime.show();
        cout<<"  运行结束时间："<<endtime.hour<<":"<<endtime.minute;
        //endtime.show();
        cout<<"  周转时间："<<cycletime<<" 带权周转时间："<<wcycletime<<endl;
    }
};

queue<Job> myjobs;//储存jobs  先进先出
queue<Job> basejobs;//原始数据

int jobsnumber;
double avgcycletime,avgwcycletime;

void readjob(){//从手动输入作业
    cout<<"请选择输入的作业数"<<endl;
    cin>>jobsnumber;
    cout<<"请依次输入作业的名字、进入时间、运行时间、优先级："<<endl;
    for(int i=0;i<jobsnumber;i++){
        string tname;
        int thour,tminute,truntime,trank;
        cin>>tname>>thour>>tminute>>truntime>>trank;
        Job tjob;
        time ttime;
        ttime.init(thour,tminute);
        tjob.init(tname,ttime,truntime,trank);
        basejobs.push(tjob);
    }
    /*while(!myjobs.empty()){
        Job job;
        job=myjobs.front();
        myjobs.pop();
        job.show();
    }*/
    /*for(vector<Job>::iterator it=vmyjobs.begin();it!=vmyjobs.end();it++){   
        Job t;
        t=*it;
        t.show();
    }*/
}


void FCFS(){//先来先服务
    myjobs=basejobs;
    queue<Job> fsfcjobs;
    Job tj;
    time lastfinish;//上一个作业的结束时间，就是下一个作业的开始时间

    //先运行第一个作业
    tj=myjobs.front();
    myjobs.pop();
    tj.begintime=tj.intime;//第一个作业的开始时间等于进入时间
    tj.endtime=tj.begintime.add(tj.runtime);//计算结束时间
    lastfinish=tj.endtime;//记下当前的上一个结束时间，即为下一个的开始时间
    tj.state="finish";
    tj.setcycle();
    fsfcjobs.push(tj);//将完成的作业加入到完成队列
    avgcycletime+=tj.cycletime;
    avgwcycletime+=tj.wcycletime;

    while(!myjobs.empty()){
        tj=myjobs.front();
        myjobs.pop();
        //cout<<lastfinish.hour<<"---"<<lastfinish.minute<<endl;
        tj.begintime=lastfinish;//开始时间为上一个作业的结束时间
        tj.endtime=tj.begintime.add(tj.runtime);//计算结束时间
        lastfinish=tj.endtime;//更新上一个作业完成时间
        //cout<<lastfinish.hour<<" "<<lastfinish.minute<<endl;
        tj.state="finish";//更新作业状态
        tj.setcycle();//计算周转时间和带权周转时间
        fsfcjobs.push(tj);//将完成的作业加入到完成队列
        avgcycletime+=tj.cycletime;
        avgwcycletime+=tj.wcycletime;
    }
    cout<<"fcfs-------------"<<endl;
    while(!fsfcjobs.empty()){
        Job job;
        job=fsfcjobs.front();
        fsfcjobs.pop();
        job.show();
    }
    cout<<"作业平均周转时间为："<<avgcycletime/jobsnumber<<" 作业平均带权周转时间为："<<avgwcycletime/jobsnumber<<endl;
}

void SJF(){
    myjobs=basejobs;
    queue<Job>sjfjobs;
    Job tj;
    time lastfinish;
    avgcycletime=0;
    avgwcycletime=0;

    //先运行第一个作业
    tj=myjobs.front();
    myjobs.pop();
    tj.begintime=tj.intime;//第一个作业的开始时间等于进入时间
    tj.endtime=tj.begintime.add(tj.runtime);//计算结束时间
    lastfinish=tj.endtime;//记下当前的上一个结束时间，即为下一个的开始时间
    tj.state="finish";
    tj.setcycle();
    sjfjobs.push(tj);//将完成的作业加入到完成队列
    avgcycletime+=tj.cycletime;
    avgwcycletime+=tj.wcycletime;

    Job jobs[10];
    int i=0;
    while (!myjobs.empty())
    {
        tj=myjobs.front();
        myjobs.pop();
        jobs[i++]=tj;
    }

    int tmintime;//记录当前运行的最短时间
    int tid;//记录短作业id
    time tmin;
    Job ttj;//保存作业

    while(sjfjobs.size()<jobsnumber){
        tmintime=1000;//每一次都更新最短时间
        for(int j=0;j<i;j++){//遍历数组
            if(jobs[j].intime.than(lastfinish)&&jobs[j].state=="wait"&&jobs[j].runtime<tmintime){//已经进入的，未运行的，运行时间短的
                tid=j;//记下id
                tmintime=jobs[j].runtime;//更新时间
            }
        }
        jobs[tid].state="finish";
        ttj=jobs[tid];//当前最短作业
        //运行作业
        ttj.begintime=lastfinish;//开始时间为上一个作业的结束时间
        ttj.endtime=ttj.begintime.add(ttj.runtime);//计算结束时间
        lastfinish=ttj.endtime;//更新上一个作业完成时间
        //cout<<lastfinish.hour<<" "<<lastfinish.minute<<endl;
        ttj.state="finish";//更新作业状态
        ttj.setcycle();//计算周转时间和带权周转时间
        sjfjobs.push(ttj);//将完成的作业加入到完成队列
        avgcycletime+=ttj.cycletime;
        avgwcycletime+=ttj.wcycletime;
    }

    cout<<"sjf-------------"<<endl;

    while(!sjfjobs.empty()){//打印
        Job job;
        job=sjfjobs.front();
        sjfjobs.pop();
        job.show();
        }
    cout<<"作业平均周转时间为："<<avgcycletime/jobsnumber<<" 作业平均带权周转时间为："<<avgwcycletime/jobsnumber<<endl;
}

void HHRN(){
    myjobs=basejobs;
    queue<Job>hhrnjobs;
    Job tj;
    time lastfinish;
    avgcycletime=0;
    avgwcycletime=0;

    //先运行第一个作业
    tj=myjobs.front();
    myjobs.pop();
    tj.begintime=tj.intime;//第一个作业的开始时间等于进入时间
    tj.endtime=tj.begintime.add(tj.runtime);//计算结束时间
    lastfinish=tj.endtime;//记下当前的上一个结束时间，即为下一个的开始时间
    tj.state="finish";
    tj.setcycle();
    hhrnjobs.push(tj);//将完成的作业加入到完成队列
    avgcycletime+=tj.cycletime;
    avgwcycletime+=tj.wcycletime;

    Job jobs[10];
    int i=0;
    while (!myjobs.empty())
    {
        tj=myjobs.front();
        myjobs.pop();
        tj.setrrn(lastfinish);
        //cout<<"响应比"<<tj.rrn<<endl;
        jobs[i++]=tj;
        
    }

    int tmaxrrn;//记录当前运行的最大响应比
    int tid;//记录作业id
    Job ttj;//保存作业

    while(hhrnjobs.size()<jobsnumber){
        tmaxrrn=0;//每一次都更新最短时间
        for(int j=0;j<i;j++){//遍历数组
            if(jobs[j].intime.than(lastfinish)&&jobs[j].state=="wait"&&jobs[j].rrn>tmaxrrn){//已经进入的，未运行的，响应比更大的
                tid=j;//记下id
                tmaxrrn=jobs[j].rrn;//更新响应比
            }
        }
        jobs[tid].state="finish";
        ttj=jobs[tid];//当前最短作业
        //运行作业
        ttj.begintime=lastfinish;//开始时间为上一个作业的结束时间
        ttj.endtime=ttj.begintime.add(ttj.runtime);//计算结束时间
        lastfinish=ttj.endtime;//更新上一个作业完成时间
        //cout<<lastfinish.hour<<" "<<lastfinish.minute<<endl;
        ttj.state="finish";//更新作业状态
        ttj.setcycle();//计算周转时间和带权周转时间
        hhrnjobs.push(ttj);//将完成的作业加入到完成队列
        avgcycletime+=ttj.cycletime;
        avgwcycletime+=ttj.wcycletime;
        
        //更新响应比
        for(int j=0;j<i;j++){//遍历数组
            if(jobs[j].state=="wait"){//未运行的
                Job t;
                t=jobs[j];
                t.setrrn(lastfinish);
                jobs[j].rrn=t.rrn;
            }
        } 
    }
    cout<<"hhrn-------------"<<endl;
    while(!hhrnjobs.empty()){//打印
        Job job;
        job=hhrnjobs.front();
        hhrnjobs.pop();
        job.show();
        }
    cout<<"作业平均周转时间为："<<avgcycletime/jobsnumber<<" 作业平均带权周转时间为："<<avgwcycletime/jobsnumber<<endl;
}

void doubleFSFC(){
    myjobs=basejobs;
    queue<Job> doublefsfcjobs;
    Job tj,cpu1,cpu2;
    time lastfinish1,lastfinish2;//上一个作业的结束时间，就是下一个作业的开始时间

    //先运行第一个作业
    cpu1=myjobs.front();
    myjobs.pop();
    cpu1.begintime=cpu1.intime;//第一个作业的开始时间等于进入时间
    cpu1.endtime=cpu1.begintime.add(cpu1.runtime);//计算结束时间
    lastfinish1=cpu1.endtime;//记下当前的上一个结束时间，即为下一个的开始时间
    cpu1.state="finish";
    cpu1.setcycle();
    doublefsfcjobs.push(cpu1);//将完成的作业加入到完成队列
    avgcycletime+=cpu1.cycletime;
    avgwcycletime+=cpu1.wcycletime;

    tj=myjobs.front();//查看第二个作业
    if(tj.intime.than(lastfinish1)){//如果在第一个作业运行过程中第二个作业到达，则作业二在cpu2运行
        cpu2=tj;
        myjobs.pop();
        cpu2.begintime=cpu2.intime;//第一个作业的开始时间等于进入时间
        time t;
        t=cpu2.begintime;
        cpu2.endtime=t.add(cpu2.runtime);//计算结束时间
        lastfinish2=cpu2.endtime;//记下当前的上一个结束时间，即为下一个的开始时间
        cpu2.state="finish";
        cpu2.setcycle();
        doublefsfcjobs.push(cpu2);//将完成的作业加入到完成队列
        avgcycletime+=cpu2.cycletime;
        avgwcycletime+=cpu2.wcycletime;
    }
    //保证lastfinish1是最先空闲的完成时间
    while(!myjobs.empty()){

        if(!lastfinish1.than(lastfinish2)){
        time t;
        t=lastfinish1;
        lastfinish1=lastfinish2;
        lastfinish2=t;
        }
    //一次运行两个作业
        cpu1=myjobs.front();
        myjobs.pop();
        cpu2=myjobs.front();
        myjobs.pop();
        //cout<<lastfinish.hour<<"---"<<lastfinish.minute<<endl;
        cpu1.begintime=lastfinish1;//开始时间为上一个作业的结束时间
        cpu1.endtime=cpu1.begintime.add(cpu1.runtime);//计算结束时间
        time t;
        t=cpu1.begintime;
        cpu1.endtime=t.add(cpu1.runtime);//计算结束时间
        lastfinish1=cpu1.endtime;//更新上一个作业完成时间
        //cout<<lastfinish.hour<<" "<<lastfinish.minute<<endl;
        cpu1.state="finish";//更新作业状态
        cpu1.setcycle();//计算周转时间和带权周转时间
        doublefsfcjobs.push(cpu1);//将完成的作业加入到完成队列
        avgcycletime+=cpu1.cycletime;
        avgwcycletime+=cpu1.wcycletime;

        cpu2.begintime=lastfinish1;//开始时间为上一个作业的结束时间
        t=cpu2.begintime;
        cpu2.endtime=t.add(cpu2.runtime);//计算结束时间
        lastfinish2=cpu2.endtime;//更新上一个作业完成时间
        //cout<<lastfinish.hour<<" "<<lastfinish.minute<<endl;
        cpu2.state="finish";//更新作业状态
        cpu2.setcycle();//计算周转时间和带权周转时间
        doublefsfcjobs.push(cpu2);//将完成的作业加入到完成队列
        avgcycletime+=cpu2.cycletime;
        avgwcycletime+=cpu2.wcycletime;
    }
    cout<<"doublefcfs-------------"<<endl;
    while(!doublefsfcjobs.empty()){
        Job job;
        job=doublefsfcjobs.front();
        doublefsfcjobs.pop();
        job.show();
    }
    cout<<"作业平均周转时间为："<<avgcycletime/jobsnumber<<" 作业平均带权周转时间为："<<avgwcycletime/jobsnumber<<endl;
}
void HrankFSFC(){
    myjobs=basejobs;
    queue<Job> hrankfcfsjobs;
    Job runJob[2];
    int runnumbers=0;
    Job tj,job1,job2;
    time t,t1,t2;
    time lastfinish;
    lastfinish.init(24,0);
    //先运行第一和第二个作业
    runJob[0]=myjobs.front();
    myjobs.pop();
    runJob[1]=myjobs.front();
    myjobs.pop();

    job1=runJob[0];
    job2=runJob[1];
    //cout<<lastfinish.hour<<"---"<<lastfinish.minute<<endl;
    job1.begintime=job1.intime;//开始时间为进入时间
    t=job1.begintime;
    t1=t.add(job1.runtime);//job1预计结束时间
    if(!t1.than(job2.intime)&&job1.rank<job2.rank){//如果第二个作业比第一个作业优先
        int restruntime;//剩余运行时间
        restruntime=job1.begintime.substract(job2.intime);//计算job1的剩余时间
        restruntime=job1.runtime-restruntime;
        job1.resruntime=restruntime;//修改job1的剩余时间
        job2.begintime=job2.intime;//job2开始运行
        t=job2.begintime;
        job2.endtime=t.add(job2.runtime);
        lastfinish=job2.endtime;
        job2.state="finish";//更新作业状态
        job2.setcycle();//计算周转时间和带权周转时间
        hrankfcfsjobs.push(job2);//将完成的作业加入到完成队列
        avgcycletime+=job2.cycletime;
        avgwcycletime+=job2.wcycletime;
        runJob[0]=job1;
        runJob[1]=myjobs.front();//将下一个加入到队列中
        myjobs.pop();
    }else{
        job1.endtime=t.add(job1.runtime);
        lastfinish=job1.endtime;
        job1.state="finish";//更新作业状态
        job1.setcycle();//计算周转时间和带权周转时间
        hrankfcfsjobs.push(job1);//将完成的作业加入到完成队列
        avgcycletime+=job1.cycletime;
        avgwcycletime+=job1.wcycletime;
        runJob[0]=runJob[1];
        runJob[1]=myjobs.front();//将下一个加入到队列中
        myjobs.pop();
    }

    //cout<<"------"<<endl;
    while(!myjobs.empty()){
        //一次进入两个作业
        job1=runJob[0];
        job2=runJob[1];
        //cout<<lastfinish.hour<<"---"<<lastfinish.minute<<endl;
        if(job1.begintime.hour==0&&job2.begintime.minute==0){
                job1.begintime=lastfinish;
            }
        if(job1.rank>=job2.rank){//如果第二个作业的优先级低于第一个，则直接运行job1

            job1.endtime=t.add(job1.resruntime);
            lastfinish=job1.endtime;
            job1.state="finish";//更新作业状态
            job1.setcycle();//计算周转时间和带权周转时间
            hrankfcfsjobs.push(job1);//将完成的作业加入到完成队列
            avgcycletime+=job1.cycletime;
            avgwcycletime+=job1.wcycletime;
            runJob[0]=runJob[1];
            runJob[1]=myjobs.front();//将下一个加入到队列中
            myjobs.pop();

        }else if(job1.rank<job2.rank){
            t=job1.begintime;
            t1=t.add(job1.resruntime);//job1预计结束时间
            if(t1.than(job2.intime)){//job1的结束时间比job2进入时间早,还是运行job1
                job1.endtime=t.add(job1.resruntime);
                lastfinish=job1.endtime;
                job1.state="finish";//更新作业状态
                job1.setcycle();//计算周转时间和带权周转时间
                hrankfcfsjobs.push(job1);//将完成的作业加入到完成队列
                avgcycletime+=job1.cycletime;
                avgwcycletime+=job1.wcycletime;
                runJob[0]=runJob[1];
                runJob[1]=myjobs.front();//将下一个加入到队列中
                myjobs.pop();
            }else{
                int restruntime;//剩余运行时间
                restruntime=lastfinish.substract(job2.intime);//计算job1的剩余时间
                restruntime=job1.runtime-restruntime;
                job1.resruntime=restruntime;//修改job1的剩余时间
                job2.begintime=job2.intime;//job2开始运行
                t=job2.begintime;
                job2.endtime=t.add(job2.runtime);
                lastfinish=job2.endtime;
                job2.state="finish";//更新作业状态
                job2.setcycle();//计算周转时间和带权周转时间
                hrankfcfsjobs.push(job2);//将完成的作业加入到完成队列
                avgcycletime+=job2.cycletime;
                avgwcycletime+=job2.wcycletime;
                runJob[0]=job1;
                runJob[1]=myjobs.front();//将下一个加入到队列中
                myjobs.pop();
            }
        }
    }
    //运行最后两个
    job1=runJob[0];
    job2=runJob[1];
    //cout<<lastfinish.hour<<"---"<<lastfinish.minute<<endl;
    if(job1.rank>=job2.rank){//如果第二个作业的优先级低于第一个，则直接运行job1
        if(job1.begintime.hour==0&&job2.begintime.minute==0){
            job1.begintime=lastfinish;
        }
        t=job1.begintime;
        job1.endtime=t.add(job1.resruntime);
        lastfinish=job1.endtime;
        job1.state="finish";//更新作业状态
        job1.setcycle();//计算周转时间和带权周转时间
        hrankfcfsjobs.push(job1);//将完成的作业加入到完成队列
        avgcycletime+=job1.cycletime;
        avgwcycletime+=job1.wcycletime;

        job2.begintime=job2.intime;
        t=job2.begintime;
        job2.endtime=t.add(job2.runtime);
        lastfinish=job2.endtime;
        job2.state="finish";//更新作业状态
        job2.setcycle();//计算周转时间和带权周转时间
        hrankfcfsjobs.push(job2);//将完成的作业加入到完成队列
        avgcycletime+=job2.cycletime;
        avgwcycletime+=job2.wcycletime;

    }else if(job1.rank<job2.rank){
        if(job1.begintime.hour==0&&job2.begintime.minute==0){
            job1.begintime=lastfinish;
        }
        t=job1.begintime;
        t1=t.add(job1.resruntime);//job1预计结束时间
        if(t1.than(job2.intime)){//job1的结束时间比job2进入时间早,还是运行job1
            t=job1.begintime;
            job1.endtime=t.add(job1.resruntime);
            lastfinish=job1.endtime;
            job1.state="finish";//更新作业状态
            job1.setcycle();//计算周转时间和带权周转时间
            hrankfcfsjobs.push(job1);//将完成的作业加入到完成队列
            avgcycletime+=job1.cycletime;
            avgwcycletime+=job1.wcycletime;

            job2.begintime=job2.intime;
            t=job2.begintime;
            job2.endtime=t.add(job2.runtime);
            lastfinish=job2.endtime;
            job2.state="finish";//更新作业状态
            job2.setcycle();//计算周转时间和带权周转时间
            hrankfcfsjobs.push(job2);//将完成的作业加入到完成队列
            avgcycletime+=job2.cycletime;
            avgwcycletime+=job2.wcycletime;

        }else{  //运行第二个
            int restruntime;//剩余运行时间
            restruntime=lastfinish.substract(job2.intime);//计算job1的剩余时间
            restruntime=job1.runtime-restruntime;
            job1.resruntime=restruntime;//更新剩余时间
            job2.begintime=job2.intime;//job2开始运行
            t=job2.begintime;
            job2.endtime=t.add(job2.runtime);
            lastfinish=job2.endtime;
            job2.state="finish";//更新作业状态
            job2.setcycle();//计算周转时间和带权周转时间
            hrankfcfsjobs.push(job2);//将完成的作业加入到完成队列
            avgcycletime+=job2.cycletime;
            avgwcycletime+=job2.wcycletime;

            job1.endtime=lastfinish.add(job1.resruntime);
            lastfinish=job1.endtime;
            job1.state="finish";//更新作业状态
            job1.setcycle();//计算周转时间和带权周转时间
            hrankfcfsjobs.push(job1);//将完成的作业加入到完成队列
            avgcycletime+=job1.cycletime;
            avgwcycletime+=job1.wcycletime;          
            }
    }

    cout<<"hrankfcfs-------------"<<endl;
    while(!hrankfcfsjobs.empty()){
        Job job;
        job=hrankfcfsjobs.front();
        hrankfcfsjobs.pop();
        job.show();
    }
    cout<<"作业平均周转时间为："<<avgcycletime/jobsnumber<<" 作业平均带权周转时间为："<<avgwcycletime/jobsnumber<<endl;
}

int main(){
    readjob();
    //FCFS();
    //SJF();
    //HHRN();
    doubleFSFC();
    HrankFSFC();
    return 0;
}